/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年03月05日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if( root == NULL )
            return res;

        queue<TreeNode *> q;
        q.push(root);
        int size = 0;
        bool flag = true;


        while(! q.empty() ){
            size = q.size();
            vector<int> tmp(size);
            TreeNode *p = NULL;
            int index = 0;
            for(int i = 0; i < size; i++){
                p = q.front();
                q.pop();
                index = flag ? i:size - i - 1;
                tmp[index] = p->val;

                if(p->left){
                    q.push(p->left);
                }
                if(p->right){
                    q.push(p->right);
                }
            }

            res.push_back(tmp);
            if(flag)
                flag = false;
            else
                flag = true;
        } 

        return res;
    }
};

